using System;
using System.Collections.Generic;
using System.Diagnostics;
using BepuUtilities.Memory;
using System.Runtime.CompilerServices;

namespace BepuUtilities.Collections
{
    /// <summary>
    /// 包含用于哈希的基本帮助器。
    /// </summary>
    public static class HashHelper
    {
        /// <summary>
        /// 重新分发哈希。用于将唯一但连续的散列转换为半随机分布。
        /// </summary>
        /// <param name="hash">要重分发的哈希。</param>
        /// <return>哈希。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int Rehash(int hash)
        {
            // 这次更新旨在解决两个问题：
            // 1)很多公共键,如整型、长整型等,都会产生连续的哈希码。
            // 连续的哈希码会导致连续的表项,这会破坏此实现的线性探测性能。
            // 2)许多常见散列具有显著模式化的输入,例如在低位中全部为0。由于该实现使用幂2大小的表,
            // 可能与POW2表大小对齐的图案可能会导致大量冲突。
            // 因此,我们对散列应用额外的加扰传递,以消除大多数这样的模式。这不能阻止恶意攻击者,但应该避免大多数巧合。
            // 请记住,此实现对性能至关重要-没有时间进行大量循环。
            // 初始倍增用于避免某些连续诱导的图案化,
            // 遵循XOR‘d旋转可以处理大多数位分布模式,加在一起非常便宜。
            // (您可能熟悉SHA2圆角中的这些旋转常数。)

            const int a = 6;
            const int b = 13;
            const int c = 25;
            uint uhash = (uint)hash * 982451653u;
            var redongled =
                ((uhash << a) | (uhash >> (32 - a))) ^
                ((uhash << b) | (uhash >> (32 - b))) ^
                ((uhash << c) | (uhash >> (32 - c)));
            return (int)redongled;
        }
    }
    /// <summary>
    /// 容器支持恒定时间,在保持快速迭代时间的同时添加和删除键值对。
    /// 以牺牲安全为代价提供非常直接的信息访问。
    /// </summary>
    /// <remarks>
    /// <para>
    /// 使用此类型时要非常小心。它在性能的祭坛上牺牲了很多;几个值得注意的问题包括：
    /// 它是一种值类型,复制它会在不加注意的情况下破坏东西,
    /// 它不能被有效地缺省构造,
    /// 它将内部结构暴露给用户修改,
    /// 它很少检查输入是否有错误,
    /// 枚举器不检查枚举中期修改,
    /// 它允许不安全的添加,如果用户不管理容量可能会中断,
    /// 它在抽象的存储器二进制大对象之上工作,该抽象的存储器二进制大对象在内部可能是可以被拉动的指针,
    /// 它不(也不能)检查所提供的内存是否返回到它来自的同一池。
    /// </para>
    /// <para>请注意,实现非常简单。它在冲突率非常低的假设下使用单步线性探测。
    /// 建议使用较大的表容量;这会牺牲一些内存以换取简单性和运行时性能。</para></注释>
    /// <typeparam name="TKey">容器持有的密钥类型。</typeparam>
    /// <typeparam name="TValue">容器保存的值的类型。</typeparam>
    /// <typeparam name="TEqualityCompeller">使用的相等测试器和哈希计算器的类型。</typeparam>
    public struct QuickDictionary<TKey, TValue, TEqualityComparer> where TKey : unmanaged where TValue : unmanaged where TEqualityComparer : IEqualityComparerRef<TKey>
    {
        /// <summary>
        /// 获取字典中的元素数。
        /// </summary>
        public int Count;

        /// <summary>
        /// 用于对哈希执行快速模运算的掩码。要求表跨度是2的幂。
        /// </summary>
        public int TableMask;

        /// <summary>
        /// 表的期望大小相对于键/值范围的大小,以2的幂表示。表容量目标将是elementCapacityTarget*2^TablePowerOffset。
        /// </summary>
        public int TablePowerOffset;

        /// <summary>
        /// 备份字典表的内存。值是根据EqualityCompeller的散列函数分发的。
        /// 包含0的插槽未使用,并且没有指向任何内容。包含较高值的窗等于1加上跨度中元素的索引。
        /// </summary>
        public Buffer<int> Table;

        /// <summary>
        /// 包含词典关键字的后备存储器。
        /// 从0到COUNT-1的索引保存实际数据。所有其他数据均未定义。
        /// </summary>
        public Buffer<TKey> Keys;

        /// <summary>
        /// 包含字典值的后备存储器。
        /// 从0到COUNT-1的索引保存实际数据。所有其他数据均未定义。
        /// </summary>
        public Buffer<TValue> Values;

        /// <summary>
        /// 用于比较和散列键的相等比较器。
        /// </summary>
        public TEqualityComparer EqualityComparer;

        /// <summary>
        /// 获取或设置列表表示形式中给定索引处的键值对。
        /// </summary>
        /// <param name="index">要从中获取对的索引。</param>
        /// <return>字典中给定索引处的对。</return>
        public KeyValuePair<TKey, TValue> this[int index]
        {
            // 您可能认为这样一个微不足道的访问器会在没有任何外部建议的情况下内联。
            // 有时候,是的。有时候,不会。：(
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            get
            {
                Debug.Assert(index >= 0 && index < Count, "Index should be within the dictionary's size.");
                return new KeyValuePair<TKey, TValue>(Keys[index], Values[index]);
            }
            [MethodImpl(MethodImplOptions.AggressiveInlining)]
            set
            {
                Debug.Assert(index >= 0 && index < Count, "Index should be within the dictionary's size.");
                Keys[index] = value.Key;
                Values[index] = value.Value;
            }
        }


        /// <summary>
        /// 创建新词典。
        /// </summary>
        /// <param name="initialKeySpan">用作字典键后备内存的范围。</param>
        /// <param name="initialValueSpan">用作字典值后备内存的范围。</param>
        /// 用作表的后备内存的<param name="initialTableSpan">范围。必须为零。</param>
        /// <param name="Compeller">用于词典的比较器。</param>
        /// <param name="tablePowerOffset">表的目标大小相对于存储的元素数。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public QuickDictionary(ref Buffer<TKey> initialKeySpan, ref Buffer<TValue> initialValueSpan, ref Buffer<int> initialTableSpan, TEqualityComparer comparer, int tablePowerOffset = 2)
        {
            ValidateSpanCapacity(ref initialKeySpan, ref initialValueSpan, ref initialTableSpan);
            Keys = initialKeySpan;
            Values = initialValueSpan;
            Table = initialTableSpan;
            Count = 0;
            TableMask = Table.Length - 1;
            TablePowerOffset = tablePowerOffset;
            EqualityComparer = comparer;
            Debug.Assert(EqualityComparer != null);
            ValidateTableIsCleared(ref initialTableSpan);
        }

        /// <summary>
        /// 使用默认构造的比较器创建新字典。
        /// </summary>
        /// <param name="initialKeySpan">用作字典键后备内存的范围。</param>
        /// <param name="initialValueSpan">用作字典值后备内存的范围。</param>
        /// 用作表的后备内存的<param name="initialTableSpan">范围。必须为零。</param>
        /// <param name="Compeller">用于词典的比较器。</param>
        /// <param name="tablePowerOffset">表的目标大小相对于存储的元素数。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public QuickDictionary(ref Buffer<TKey> initialKeySpan, ref Buffer<TValue> initialValueSpan, ref Buffer<int> initialTableSpan, int tablePowerOffset = 2)
            : this(ref initialKeySpan, ref initialValueSpan, ref initialTableSpan, default, tablePowerOffset)
        {
        }

        /// <summary>
        /// 创建新词典。
        /// </summary>
        /// <param name="initialCapacity">键和值的初始目标大小。初始缓冲区的大小至少与initialCapacity相同。</param>
        /// <param name="tableSizePower">相对于初始容量的目标容量,其幂为2。初始表缓冲区的大小将至少是初始容量的2^tableSizePower倍。</param>
        /// <param name="Compeller">要在词典中使用的比较器。</param>
        /// <param name="pool">用于跨度的池。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public QuickDictionary(int initialCapacity, int tableSizePower, IUnmanagedMemoryPool pool, TEqualityComparer comparer)
        {
            pool.TakeAtLeast<TKey>(initialCapacity, out var keySpan);
            pool.TakeAtLeast<TValue>(keySpan.Length, out var valueSpan);
            pool.TakeAtLeast<int>(keySpan.Length << tableSizePower, out var tableSpan);
            // 不能保证桌子是干净的;把它清理干净。
            tableSpan.Clear(0, tableSpan.Length);
            this = new QuickDictionary<TKey, TValue, TEqualityComparer>(ref keySpan, ref valueSpan, ref tableSpan, comparer, tableSizePower);
        }

        /// <summary>
        /// 使用默认构造的比较器创建新字典。
        /// </summary>
        /// <param name="initialCapacity">键和值的初始目标大小。初始缓冲区的大小至少与initialCapacity相同。</param>
        /// <param name="tableSizePower">相对于初始容量的目标容量,其幂为2。初始表缓冲区的大小将至少是初始容量的2^tableSizePower倍。</param>
        /// <param name="Compeller">要在词典中使用的比较器。</param>
        /// <param name="pool">用于跨度的池。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public QuickDictionary(int initialCapacity, int tableSizePower, IUnmanagedMemoryPool pool)
            : this(initialCapacity, tableSizePower, pool, default)
        {
        }

        /// <summary>
        /// 使用默认构造的比较器创建新字典。
        /// </summary>
        /// <param name="initialCapacity">键和值的初始目标大小。初始缓冲区的大小至少与initialCapacity相同。</param>
        /// <param name="Compeller">要在词典中使用的比较器。</param>
        /// <param name="pool">用于跨度的池。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public QuickDictionary(int initialCapacity, IUnmanagedMemoryPool pool)
            : this(initialCapacity, 2, pool, default)
        {
        }


        /// <summary>
        /// 将字典的后备内存范围换成新的范围。
        /// 如果新跨度较小,则会截断字典的计数,并删除多余的元素。
        /// 旧跨度不会被清除或返回到任何池;如果需要将其池化或清除,则用户必须处理它。
        /// </summary>
        /// <param name="newKeySpan">用于密钥的新范围。</param>
        /// <param name="newValueSpan">用于值的新范围。</param>
        /// <param name="newTableSpan">用于表的新span。必须为零。</param>
        /// <param name="oldKeySpan">用于密钥的上一个范围。</param>
        /// <param name="oldValueSpan">用于值的上一个范围。</param>
        /// <param name="oldTableSpan">表使用的上一个跨度。</param>
        public void Resize(ref Buffer<TKey> newKeySpan, ref Buffer<TValue> newValueSpan, ref Buffer<int> newTableSpan,
            out Buffer<TKey> oldKeySpan, out Buffer<TValue> oldValueSpan, out Buffer<int> oldTableSpan)
        {
            ValidateSpanCapacity(ref newKeySpan, ref newValueSpan, ref newTableSpan);
            ValidateTableIsCleared(ref newTableSpan);
            var oldDictionary = this;
            Keys = newKeySpan;
            Values = newValueSpan;
            Table = newTableSpan;
            Count = 0;
            TableMask = newTableSpan.Length - 1;
            var newCount = oldDictionary.Count > newKeySpan.Length ? newKeySpan.Length : oldDictionary.Count;

            // 不幸的是,我们真的不能直接复制;后备表依赖于模运算。
            // 从技术上讲,我们可以复制常规字典,然后依靠部分添加来管理睡觉,但是废话连篇！
            // 无论如何,只要有可能,都应该尽量避免在集合和字典上调整大小。不是很快。
            for (int i = 0; i < newCount; ++i)
            {
                // 我们假设ref add将在这里合理地内联。这实际上不能保证,但我们会咬紧牙关。
                // (从技术上讲,您可以在Unsafe.SizeOf<T>上进行分支,这应该会导致编译时专用的零开销实现……但是喵！)
                AddUnsafelyRef(ref oldDictionary.Keys[i], oldDictionary.Values[i]);
            }
            oldKeySpan = oldDictionary.Keys;
            oldValueSpan = oldDictionary.Values;
            oldTableSpan = oldDictionary.Table;

        }

        /// <summary>
        /// 针对给定大小调整字典的后备数组的大小。
        /// 如果新跨度较小,则会截断字典的计数,并删除多余的元素。
        /// </summary>
        /// <param name="newsize">新对象内存挡路的最小大小。实际大小可能更大。</param>
        /// <param name="pool">用于跨度的池。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Resize(int newSize, IUnmanagedMemoryPool pool)
        {
            var targetKeyCapacity = pool.GetCapacityForCount<TKey>(newSize);
            if (targetKeyCapacity != Keys.Length)
            {
                pool.TakeAtLeast<TKey>(newSize, out var newKeySpan);
                pool.TakeAtLeast<TValue>(newKeySpan.Length, out var newValueSpan);
                pool.TakeAtLeast<int>(newKeySpan.Length << TablePowerOffset, out var newTableSpan);
                // 不能保证从池中检索的表是干净的。把它清理干净！
                newTableSpan.Clear(0, newTableSpan.Length);
                var oldDictionary = this;
                Resize(ref newKeySpan, ref newValueSpan, ref newTableSpan, out var oldKeySpan, out var oldValueSpan, out var oldTableSpan);
                oldDictionary.Dispose(pool);
            }
        }

        /// <summary>
        /// 将与字典关联的资源返回到池。
        /// </summary>
        /// <param name="keyPool">用于键跨度的池。</param>
        /// <param name="valuePool">用于值范围的池。</param>
        /// <param name="tablePool">用于表跨度的池。</param>
        /// <typeparam name="TKeyPool">用于键跨度的池的类型。</typeparam>
        /// <typeparam name="TValuePool">用于值范围的池的类型。</typeparam>
        /// <typeparam name="TablePool">用于表跨度的池的类型。</typeparam>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Dispose(IUnmanagedMemoryPool pool)
        {
            pool.Return(ref Keys);
            pool.Return(ref Values);
            pool.Return(ref Table);
        }

        /// <summary>
        /// 确保字典有足够的空间来容纳指定数量的元素。
        /// </summary>     
        /// <param name="pool">用于跨度的池。</param>
        /// <param name="count">要保存的元素数。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void EnsureCapacity(int count, IUnmanagedMemoryPool pool)
        {
            if (count > Keys.Length)
            {
                Resize(count, pool);
            }
        }

        /// <summary>
        /// 将内部缓冲区缩小到可接受的最小大小,并将旧缓冲区释放到池中。
        /// </summary>
        /// <param name="pool">用于跨度的池。</param>
        /// <param name="element">要添加的元素。</param>
        public void Compact(IUnmanagedMemoryPool pool)
        {
            Validate();
            var targetKeyCapacity = pool.GetCapacityForCount<TKey>(Count);
            if (targetKeyCapacity < Keys.Length)
                Resize(Count, pool);
        }



        /// <summary>
        /// 获取表中元素的索引。
        /// </summary>
        /// <param name="element">要查找的元素。</param>
        /// <param name="tableIndex">重定向表中元素的索引,如果不存在,则为要添加该元素的位置的索引。</param>
        /// <param name="elementIndex">元素数组中元素的索引(如果存在);否则为-1。</param>
        /// <return>如果该元素存在于字典中,则为True;如果不存在,则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool GetTableIndices(ref TKey element, out int tableIndex, out int elementIndex)
        {
            Validate();

            // 表长保证是2的幂,因此模数是一个简单的二元运算。
            tableIndex = HashHelper.Rehash(EqualityComparer.Hash(ref element)) & TableMask;
            // 表中的0表示"未采用";所有其他值向上偏移1。也就是说,1实际上是索引0,2实际上是索引1,依此类推。
            // 这比使用负数进行标记更可取,因为清除缓冲区将包含全0。
            while ((elementIndex = Table[tableIndex]) > 0)
            {
                // 此表索引被采用。这是指定的元素吗？
                // 记住解码对象索引。
                if (EqualityComparer.Equals(ref Keys[--elementIndex], ref element))
                {
                    return true;
                }
                tableIndex = (tableIndex + 1) & TableMask;
            }
            elementIndex = -1;
            return false;
        }

        /// <summary>
        /// 获取字典值列表中的键的索引(如果存在)。
        /// </summary>
        /// <param name="key">要获取其索引的键。</param>
        /// <return>如果键存在于字典中,则为键的索引,否则为-1。</return>
        public int IndexOf(TKey key)
        {
            Validate();
            GetTableIndices(ref key, out int tableIndex, out int objectIndex);
            return objectIndex;
        }


        /// <summary>
        /// 获取字典值列表中的键的索引(如果存在)。
        /// </summary>
        /// <param name="key">要获取其索引的键。</param>
        /// <return>如果键存在于字典中,则为键的索引,否则为-1。</return>
        public int IndexOfRef(ref TKey key)
        {
            Validate();
            GetTableIndices(ref key, out int tableIndex, out int objectIndex);
            return objectIndex;
        }

        /// <summary>
        /// 检查给定的键是否已属于字典。
        /// </summary>
        /// <param name="key">要测试的密钥。</param>
        /// <return>如果键已属于字典,则为True,否则为False。</return>
        public bool ContainsKey(TKey key)
        {
            Validate();
            return GetTableIndices(ref key, out int tableIndex, out int objectIndex);
        }

        /// <summary>
        /// 检查给定的键是否已属于字典。
        /// </summary>
        /// <param name="key">要测试的密钥。</param>
        /// <return>如果键已属于字典,则为True,否则为False。</return>
        public bool ContainsKeyRef(ref TKey key)
        {
            Validate();
            return GetTableIndices(ref key, out int tableIndex, out int objectIndex);
        }

        /// <summary>
        /// 尝试检索与键关联的值(如果存在)。
        /// </summary>
        /// <param name="key">要查找的键。</param>
        /// <param name="value">与指定键关联的值。</param>
        /// <return>如果找到值,则为True,否则为False。</return>
        public bool TryGetValue(TKey key, out TValue value)
        {
            Validate();
            if (GetTableIndices(ref key, out int tableIndex, out int elementIndex))
            {
                value = Values[elementIndex];
                return true;
            }
            value = default;
            return false;
        }

        /// <summary>
        /// 尝试检索与键关联的值(如果存在)。
        /// </summary>
        /// <param name="key">要查找的键。</param>
        /// <param name="value">与指定键关联的值。</param>
        /// <return>如果找到值,则为True,否则为False。</return>
        public bool TryGetValueRef(ref TKey key, out TValue value)
        {
            Validate();
            if (GetTableIndices(ref key, out int tableIndex, out int elementIndex))
            {
                value = Values[elementIndex];
                return true;
            }
            value = default;
            return false;
        }

        /// <summary>
        /// 将一对添加到词典中。如果密钥的一个版本(相同的散列码,比较器的‘相等’)已经存在,
        /// 现有的对将由给定的版本替换。
        /// </summary>
        /// <param name="key">要添加的密钥对。</param>
        /// <param name="value">要添加的对的值。</param>
        /// <return>如果该密钥对已添加到字典中,则为True;如果密钥已存在且其对已被替换,则为False。</return>
        // [MethodImpl(MethodImplOptions.AggressiveInlining)]//TODO：测试全链内联的性能。
        public bool AddAndReplaceUnsafelyRef(ref TKey key, in TValue value)
        {
            Validate();
            ValidateUnsafeAdd();

            if (GetTableIndices(ref key, out int tableIndex, out int elementIndex))
            {
                // 已经到场了！
                Keys[elementIndex] = key;
                Values[elementIndex] = value;
                return false;
            }

            // 字典里没有。加进去！
            Keys[Count] = key;
            Values[Count] = value;
            // 使用编码-所有索引都偏移1,因为0表示"空"。
            Table[tableIndex] = ++Count;
            return true;
        }

        /// <summary>
        /// 将一对添加到词典中。如果密钥的一个版本(相同的散列码,比较器的‘相等’)已经存在,
        /// 现有的对将由给定的版本替换。
        /// </summary>
        /// <param name="key">要添加的密钥对。</param>
        /// <param name="value">要添加的对的值。</param>
        /// <return>如果该密钥对已添加到字典中,则为True;如果密钥已存在且其对已被替换,则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool AddAndReplaceUnsafely(TKey key, in TValue value)
        {
            return AddAndReplaceUnsafelyRef(ref key, value);
        }

        /// <summary>
        /// 如果词典中不存在对,则将其添加到词典中。
        /// </summary>
        /// <param name="key">要添加的密钥对。</param>
        /// <param name="value">要添加的对的值。</param>
        /// <return>如果该对已添加到词典,则为True;如果密钥已存在,则为False。</return>
        // [MethodImpl(MethodImplOptions.AggressiveInlining)]//TODO：测试全链内联的性能。
        public bool AddUnsafelyRef(ref TKey key, in TValue value)
        {
            Validate();
            ValidateUnsafeAdd();
            if (GetTableIndices(ref key, out int tableIndex, out int elementIndex))
            {
                // 已经到场了！
                return false;
            }

            // 字典里没有。加进去！
            Keys[Count] = key;
            Values[Count] = value;
            // 使用编码-所有索引都偏移1,因为0表示"空"。
            Table[tableIndex] = ++Count;
            return true;
        }

        /// <summary>
        /// 如果词典中不存在对,则将其添加到词典中。
        /// </summary>
        /// <param name="key">要添加的密钥对。</param>
        /// <param name="value">要添加的对的值。</param>
        /// <return>如果该对已添加到词典,则为True;如果密钥已存在,则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool AddUnsafely(TKey key, in TValue value)
        {
            return AddUnsafelyRef(ref key, value);
        }

        /// <summary>
        /// 将一对添加到词典中。如果密钥的一个版本(相同的散列码,比较器的‘相等’)已经存在,
        /// 现有的对将由给定的版本替换。
        /// </summary>
        /// <param name="key">要添加的密钥对。</param>
        /// <param name="value">要添加的对的值。</param>
        /// <param name="pool">用于跨度的池。</param>
        /// <return>如果该密钥对已添加到字典中,则为True;如果密钥已存在且其对已被替换,则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool AddAndReplaceRef(ref TKey key, in TValue value, IUnmanagedMemoryPool pool)
        {
            if (Count == Keys.Length)
            {
                // 没有地方了;调整大小。
                Resize(Count * 2, pool);

                // 请注意,这是在找到任何索引之前进行测试的。
                // 如果我们只是在确定要添加它之后才调整大小,
                // 潜在的调整大小将使计算的索引无效。
            }
            return AddAndReplaceUnsafelyRef(ref key, value);
        }

        /// <summary>
        /// 将一对添加到词典中。如果密钥的一个版本(相同的散列码,比较器的‘相等’)已经存在,
        /// 现有的对将由给定的版本替换。
        /// </summary>
        /// <param name="key">要添加的密钥对。</param>
        /// <param name="value">要添加的对的值。</param>
        /// <param name="pool">用于跨度的池。</param>
        /// <return>如果该密钥对已添加到字典中,则为True;如果密钥已存在且其对已被替换,则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool AddAndReplace(TKey key, in TValue value, IUnmanagedMemoryPool pool)
        {
            return AddAndReplaceRef(ref key, value, pool);
        }

        /// <summary>
        /// 如果词典中不存在对,则将其添加到词典中。
        /// </summary>
        /// <param name="key">要添加的密钥对。</param>
        /// <param name="value">要添加的对的值。</param>
        /// <param name="pool">用于跨度的池。</param>
        /// <typeparam name="TPool">用于跨度的池的类型。</typeparam>
        /// <return>如果该对已添加到词典,则为True;如果密钥已存在,则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool AddRef(ref TKey key, in TValue value, IUnmanagedMemoryPool pool)
        {
            Validate();

            if (Count == Keys.Length)
            {
                // 没有地方了;调整大小。
                Resize(Count * 2, pool);

                // 请注意,这是在找到任何索引之前进行测试的。
                // 如果我们只是在确定要添加它之后才调整大小,
                // 潜在的调整大小将使计算的索引无效。
            }
            return AddUnsafelyRef(ref key, value);
        }

        /// <summary>
        /// 如果词典中不存在对,则将其添加到词典中。
        /// </summary>
        /// <param name="key">要添加的密钥对。</param>
        /// <param name="value">要添加的对的值。</param>
        /// <param name="pool">从中提取资源和将资源返回到的池。</param>
        /// <typeparam name="TPool">要使用的池的类型。</typeparam>
        /// <return>如果该对已添加到词典,则为True;如果密钥已存在,则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool Add(TKey key, in TValue value, IUnmanagedMemoryPool pool)
        {
            return AddRef(ref key, value, pool);
        }

        // 注意：尽管这是唯一的移除礼物,但它被命名为"FastRemove"而不是"Remove"的原因是
        // 稍后可能存在保存"删除"的命令。那将是一个非常狡猾的突破性变化。

        /// <summary>
        /// 根据元素的表和元素索引从字典中删除元素。仅当表和元素索引有效时才能使用。
        /// </summary>
        /// <param name="tableIndex">与要删除的现有元素关联的表项的索引。</param>
        /// <param name="elementIndex">要在连续键/值数组中删除的现有元素的索引。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void FastRemove(int tableIndex, int elementIndex)
        {
            Debug.Assert(GetTableIndices(ref Keys[elementIndex], out var debugTableIndex, out var debugElementIndex) && debugTableIndex == tableIndex && debugElementIndex == elementIndex,
                "The table index and element index used to directly remove must match an actual key.");
            // 添加和删除必须同时维护一个属性：
            // 所有项都位于它们所需的索引处(由散列定义),或者它们都包含在从所需索引起顺时针方向连续的挡路中。
            // 移除器通过顺时针搜索查找可以向后移动的项目来填补它们造成的空白。
            // 顺时针搜索要填满此位置的项目。搜索必须继续,直到找到缺口。
            int moveCandidateIndex;
            int gapIndex = tableIndex;
            // 顺时针搜索。
            while ((moveCandidateIndex = Table[tableIndex = (tableIndex + 1) & TableMask]) > 0)
            {
                // 这个插槽里有东西。它的实际指数是多少？
                --moveCandidateIndex;
                int desiredIndex = HashHelper.Rehash(EqualityComparer.Hash(ref Keys[moveCandidateIndex])) & TableMask;

                // 如果将此元素移动到间隙,是否会更接近其实际索引？
                // 要找出答案,请计算距间隙的顺时针距离和距理想位置的顺时针距离。

                var distanceFromGap = (tableIndex - gapIndex) & TableMask;
                var distanceFromIdeal = (tableIndex - desiredIndex) & TableMask;
                if (distanceFromGap <= distanceFromIdeal)
                {
                    // 到空隙的距离小于或等于到理想位置的距离,所以只需移动到空隙即可。
                    Table[gapIndex] = Table[tableIndex];
                    gapIndex = tableIndex;
                }

            }
            // 清除拆卸留下的台面间隙。
            Table[gapIndex] = 0;
            // 如果删除的对象不是最后一个对象,则将最后一个元素交换到删除对象的元素数组索引中。
            --Count;
            if (elementIndex < Count)
            {
                Keys[elementIndex] = Keys[Count];
                Values[elementIndex] = Values[Count];
                // 在表中找到交换的对象并更新其索引。
                GetTableIndices(ref Keys[elementIndex], out tableIndex, out int oldObjectIndex);
                Table[tableIndex] = elementIndex + 1; // 记住编码！所有索引偏移1。
            }
            // 清除元素集中的最后一个槽。
            Keys[Count] = default;
            Values[Count] = default;
        }

        /// <summary>
        /// 如果属于字典,则从字典中删除与键关联的对。
        /// 不保留字典中元素的顺序。
        /// </summary>
        /// <param name="key">要删除的密钥对。</param>
        /// <return>如果找到并删除了键,则为True,否则为False。</return>
        public bool FastRemoveRef(ref TKey key)
        {
            Validate();
            // 找到它。
            if (GetTableIndices(ref key, out int tableIndex, out int elementIndex))
            {
                // 我们找到那个物体了！
                FastRemove(tableIndex, elementIndex);
                return true;
            }
            return false;
        }

        /// <summary>
        /// 如果属于字典,则从字典中删除与键关联的对。
        /// 不保留字典中元素的顺序。
        /// </summary>
        /// <param name="key">要删除的密钥对。</param>
        /// <return>如果找到并删除了键,则为True,否则为False。</return>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public bool FastRemove(TKey key)
        {
            return FastRemoveRef(ref key);
        }

        /// <summary>
        /// 从字典中删除所有元素。
        /// </summary>
        public void Clear()
        {
            // 虽然当稀疏时从字典中移除单个元素可能很吸引人,
            // 在整张桌子上使用暴力清理几乎总是更快。而且要简单得多！
            Table.Clear(0, Table.Length);
            Keys.Clear(0, Count);
            Values.Clear(0, Count);
            Count = 0;
        }

        /// <summary>
        /// 从字典中移除所有元素,而不修改键或值数组的内容。
        /// </summary>
        public void FastClear()
        {
            Table.Clear(0, Table.Length);
            Count = 0;
        }

        /// <summary>
        /// 获取跨距包装的键和值。
        /// </summary>
        /// <param name="key">字典中的密钥。</param>
        /// <param name="Values">字典中的值。</param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public unsafe void AsSpans(out Span<TKey> keys, out Span<TValue> values)
        {
            keys = new Span<TKey>(Keys.Memory, Count);
            values = new Span<TValue>(Values.Memory, Count);
        }

        public Enumerator GetEnumerator()
        {
            Validate();
            return new Enumerator(ref Keys, ref Values, Count);
        }

        public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
        {
            private readonly Buffer<TKey> keys;
            private readonly Buffer<TValue> values;
            private readonly int count;
            private int index;

            public Enumerator(ref Buffer<TKey> keys, ref Buffer<TValue> values, int count)
            {
                this.keys = keys;
                this.values = values;
                this.count = count;

                index = -1;
            }

            public KeyValuePair<TKey, TValue> Current
            {
                get { return new KeyValuePair<TKey, TValue>(keys[index], values[index]); }
            }

            public void Dispose()
            {
            }

            object System.Collections.IEnumerator.Current
            {
                get { return Current; }
            }

            public bool MoveNext()
            {
                return ++index < count;
            }

            public void Reset()
            {
                index = -1;
            }
        }
        [Conditional("DEBUG")]
        static void ValidateSpanCapacity(ref Buffer<TKey> keySpan, ref Buffer<TValue> valueSpan, ref Buffer<int> tableSpan)
        {
            Debug.Assert(tableSpan.Length >= keySpan.Length, "The table span must be at least as large as the key span.");
            Debug.Assert(valueSpan.Length >= keySpan.Length, "The value span must be at least as large as the key span.");
            Debug.Assert((tableSpan.Length & (tableSpan.Length - 1)) == 0, "Dictionaries depend upon power of 2 backing table span sizes for efficient modulo operations.");
        }

        [Conditional("DEBUG")]
        private void Validate()
        {
            Debug.Assert(Keys.Length != 0 && Values.Length != 0 && Table.Length != 0, "The QuickDictionary must have its internal buffers and pools available; default-constructed or disposed QuickDictionary should not be used.");
            ValidateSpanCapacity(ref Keys, ref Values, ref Table);
        }


        [Conditional("DEBUG")]
        void ValidateUnsafeAdd()
        {
            Debug.Assert(Count < Keys.Length, "Unsafe adders can only be used if the capacity is guaranteed to hold the new size.");
        }



        [Conditional("DEBUG")]
        void ValidateTableIsCleared(ref Buffer<int> span)
        {
            for (int i = 0; i < span.Length; ++i)
            {
                Debug.Assert(span[i] == 0, "The table provided to the set must be cleared.");
            }
        }




    }
}
